[题解]洛谷P1352 没有上司的舞会

这是一道很适合拿来练习树形dp的题目。

题意解读

首先我们读一下题。题意并不难懂，但有一点需要注意：一个职员不能参加舞会，当且仅当他的直接上司参加了舞会，与更高级的上司去不去舞会无关。

为什么这道题可以用dp求解？下面简单分析一下：

一个职员组成的子树能够贡献的最大快乐指数可以由其下属组成的子树的最大快乐指数转移来，因此满足最优子结构；
一个职员组成的子树能够贡献的最大快乐指数只与其下属组成的子树的最大快乐指数有关，与其上司的状态无关(但前提是正确地定义了状态)，因此满足无后效性。

综上所述，这道题可以用dp求解。

解题思路

定义$dp[i][0]$表示当$i$号职员不去时，它所组成的子树能够贡献的最大快乐指数；定义$dp[i][1]$表示当$i$号职员去时，它所组成的子树能够贡献的最大快乐指数。整个问题的答案就是根节点$r$的$\max \left \{ dp[r][0],dp[r][1] \right \}$。

当一个职员不去时，他的所有直接下属都可以去，但去了也不一定会达成最优解，因为快乐指数有可能是负数。所以我们要给去和不去的情况取$max$值；
当一个职员去时，他的所有直接下属都不能去，所以只能把下属不去时的答案和自己单独去时贡献的快乐指数加起来。

从而可以得出转移方程:

$dp[i][0] = \sum \max \left\{ dp[j][0],dp[j][1] \right\}$ $dp[i][1] = r_i + \sum dp[j][0]$ $\texttt{(这里的j为i号职员的任意下属)}$

那么如果我们只用一维，即用$dp[i]$表示$i$号职员组成的子树能够贡献的最大快乐指数，可以吗？~~答案当然是不可以。~~
原因：这样的状态具有后效性。一个职员组成的子树所能贡献的最大快乐指数，会受到直接上司的影响。对于本题，如果我们再加一维，并合理定义出正确的状态，就可以消除无后效性。

代码实现

本题dp部分的代码比较容易实现，稍微需要一点技巧的是找根节点等操作。定义$ind[i]$表示节点$i$的在图中的入度，则树根的入度为$0$，我们只需要找到满足$ind[i]==0$的节点就好了。关于存储方式，我使用的是邻接表存树。下面放上dp核心代码：

void mdp(int x) {
    dp[x][1] = r[x];
    if (head[x]) {
        for (int i = head[x]; i != 0; i = edges[i].next)  mdp(edges[i].to);
        for (int i = head[x]; i != 0; i = edges[i].next) {
            dp[x][0] += max(dp[edges[i].to][0], dp[edges[i].to][1]);
            dp[x][1] += dp[edges[i].to][0];
        }
    }
}

题外话

这篇题解本来是打算交到洛谷上面的，结果以重复解法为由被退回了。不过本人可以确定本题在洛谷上一部分题解的质量远低与这篇题解。很多题解直接给出了状态转移方程(方程中各个参数的含义也没说清楚，是想让我猜猜看？)，却连如何推出方程都一字未提。有的题解(不仅是此题的题解)甚至连主要思路和代码注释都没有，直接干脆利落地放上AC代码，也可以审核通过。
在此希望各位在写题解时尽量写得详细一些，让我们蒟蒻也可以看懂。